package com.wj.linear;

/**
 * 可排序的双向链表
 * @author wen.jie
 * @date 2021/8/9 21:31
 */
public class SortedDoublyLinkedList<T extends Comparable<T>> extends DoublyLinkedList<T>{

    @Override
    public void add(T t){
        if (isEmpty()){
            Node<T> node = new Node<>(t, head, null);
            head.next = node;
            last = node;
        }else {
            sort(t, head.next);
        }
        size++;
    }

    private void sort(T t, Node<T> node) {
        if(node.next == null){
            if(node.item.compareTo(t) < 0)
                putLast(t);
            else
                insert(t, last.pre, last);
        }else {
            if(node.item.compareTo(t) < 0)
                sort(t, node.next);
            else
                insert(t, node.pre, node);
        }
    }
}
